#include <stdio.h>
#include <stdlib.h>
#include "mystack.h"

//顺序栈的初始化 ，建立一个空的顺序栈
SEQSTACK *init_seqstack()
{
    SEQSTACK *L;
    L=(SEQSTACK *)malloc(sizeof(SEQSTACK));/*动态分配内存空间*/
    L->top=0;//线性表的长度为0
    return L;
}

//入栈操作，不成功输出提示语
void push_seqstack(SEQSTACK *ss,datatype x)
{
    if(full_seqstack(ss)!=0)
    {
        printf("顺序栈已满，不能入栈\n");
    }
    else
    {
        ss->a[ss->top]=x;
        ss->top++;
    }
}

//出栈操作，成功返回出栈的元素，不成功输出提示语
datatype pop_seqstack(SEQSTACK *ss)
{
    if(empty_seqstack(ss)!=0)
        printf("顺序栈已空，不能出栈\n");
    else
    {
        ss->top--;
        return ss->a[ss->top];
    }
}

//得到栈顶元素
datatype gettop_seqstack(SEQSTACK *ss)
{
    return ss->a[ss->top-1];
}

/*判断栈是否已满，返回值为0代表不满，为非0代表为满*/
int full_seqstack(SEQSTACK *ss)
{
    if(ss->top==MAXSIZE)
        return 1;
    else
        return 0;

}

/*判断栈是否为空，返回值为0代表不空，为非0代表为空*/
int empty_seqstack(SEQSTACK *ss)
{
     if(ss->top==0)
        return 1;
     else
        return 0;
}

//输出栈中元素，从栈底开始到栈顶
void print_seqstack(SEQSTACK *ss)
{
    int i,len;
    len=ss->top;
    for(i=0;i<len;i++)
        printf("%d  ",ss->a[i]);
    printf("\n");
}

//链栈的初始化 ，建立一个空的链栈
LINKSTACK *init_linkstack()
{
    LINKSTACK *ls;
    NODE *temp;
    ls=(LINKSTACK *)malloc(sizeof(LINKSTACK));
    temp=(NODE *)malloc(sizeof(NODE));
    temp->next=NULL;
    ls->top=temp;
    ls->length=0;
    return ls;
}

//入栈操作，不成功输出提示语
void push_linkstack(LINKSTACK *ss,datatype x)
{
    NODE *p;//生成的新结点
    p=(NODE *)malloc(sizeof(NODE));//给新结点动态分配内存区域
    p->data=x;//插入的值放到新结点的数据域
    p->next=ss->top->next;//把新结点链接到栈顶
    ss->top->next=p;//改变栈顶结点指向
    ss->length++;//栈的长度加1
}

//出栈操作，成功返回出栈的元素，不成功输出提示语
datatype pop_linkstack(LINKSTACK *ss)
{
    NODE *p;//定义一个节点保存要删除的结点
    datatype x;//保存删除结点数据域的值，用于返回
    if(empty_linkstack(ss)!=0)
        printf("链栈已空，不能出栈\n");
    else
    {
        p=ss->top->next;//保存要删除的结点
        ss->top->next=p->next;//改变栈顶结点指向，指向目前第一个结点的下一个结点
        x=p->data;//保存要删除结点数据域的值
        free(p);//释放删除节点空间
        ss->length--;//栈的长度减1
        return x;//返回删除结点数据域的值
    }
}

//得到栈顶元素
datatype gettop_linkstack(LINKSTACK *ss)
{
    return ss->top->next->data;//返回栈中第一个结点数据域的值
}

//判断栈是否为空，返回0代表不空，非0代表为空
int empty_linkstack(LINKSTACK *ss)
{
    if(ss->length==0)
        return 1;
    else
        return 0;
}

//输出栈中元素，从栈底开始到栈顶
void print_linkstack(LINKSTACK *ss)
{
    NODE *temp;//临时结点，用于移动
    temp=ss->top->next;//指向栈顶结点的后继结点
    while(temp!=NULL) //循环条件
    {
        printf("%d  ",temp->data);
        temp=temp->next;//依次往后移动
    }
    printf("\n");
}
